package com.wfm.leetcode.editor.cn;

import com.wfm.common.TreeNode;

/**
 * 这题让我有点明白二叉树的前序后续遍历操作了
 * 写在递归前面的，则是每次遍历到一个节点，都会先判断一下
 * 写在递归后面的，则是每次收集到左右节点后，的后续操作
 *
 * 比如本题
 * 写在前面的有两个判断语句，第一个遇到空返回，第二个遇到待求节点中的任何一个返回。
 *    因此例题中遇到左子树5就返回了，不会遍历到6和2。右边也是只会遇到1就返回，不会遇到0和8
 * 得到left和right结果后，
 *    如果左子树和右子树都包含待求的点，则3就是他们的公共祖先
 *    如果只有一个节点包含待求节点，那么就把该节点转态往上带，
 *
 *
 */
public class P剑指Offer68II二叉树的最近公共祖先{
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 这题除了一股脑先进去，再判断条件外，还带有返回值，所以在递归的后面需要处理返回值
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode dfs = dfs(root, p, q);
        return dfs;
    }
    TreeNode dfs(TreeNode root,TreeNode p ,TreeNode q){
        if(root==null) return null;
        if(root.val==p.val||root.val==q.val){
            return root;
        }

        TreeNode l = dfs(root.left,p,q);
        TreeNode r = dfs(root.right,p,q);

        // p q在root的左右孩子里
        if(l!=null&&r!=null){
            return root;
        }
        // root = p或者q
        if(l==null) return r;
        return l;
    }

    //    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if(root==null){
//            return null;
//        }
//        if(root.val==p.val||root.val==q.val){
//            return root;
//        }
//        TreeNode left = lowestCommonAncestor(root.left, p, q);
//        TreeNode right = lowestCommonAncestor(root.right, p, q);
//        if(left!=null&&right!=null){
//            return root;
//        }
//        if(left==null) return right;
//        return left;
//    }
}
//leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) { 
        Solution solution = new P剑指Offer68II二叉树的最近公共祖先().new Solution();
    }
}